package mianshi;

/**
 * description:
 * author:张腾
 * date:2021-07-18
 */

import niuke.ListNode;

/**
 * 给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。
 */
public class _02_08 {
    public ListNode detectCycle(ListNode head) {
        if (head==null) return head;
        ListNode fast = head, slow = head;
        while (fast.next!=null&&fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;

            if (fast==slow){
                fast = head;
                while (fast!=slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}
